package com.sicheng.lc.周赛.分类.思维.最大子段和;

import java.util.ArrayList;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/6/15 13:19
 */
public class 最大波动的子字符串 {
    //https://leetcode.cn/problems/substring-with-largest-variance/
    //大致思路
    //最大波动只和字符A,B有关
    //将A,B的价值是1,-1
    // A B一共有26*25种组合情况
    // 原字符串是ababab(a,b)或者(b,a) ==> 1，-1，1，-1，1，-1或者 -1,1,-1,1,-1,1
    //转化成求数组的最大子段和 并且字段和中必须包含A,B
    // 特判原串只有1种字符
    // 复杂度 组合数 A(26,2) * s.length

    public int largestVariance(String s) {
        int max = -1;
        int[] chars = new int[26];
        ArrayList<Integer> arr = new ArrayList<>();
        //原串中字符种类数
        int count = 0;

        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i) - 'a';
            if (chars[index] == 0) {
                arr.add(index);
                count++;
            }
            chars[index]++;
            if (count == 26)
                break;
        }
        if (count == 1)
            return 0;

        for (int i = 0; i < arr.size() - 1; i++) {
            for (int j = i + 1; j < arr.size(); j++) {
                int v = largestVariance(s, arr.get(i), arr.get(j));
                int w = largestVariance(s, arr.get(j), arr.get(i));
                max = Math.max(max, Math.max(v, w));
            }
        }
        return max;
    }

    public int largestVariance(String s, int a, int b) {
        int pre = 0;
        int max = Integer.MIN_VALUE;
        // 子数组中要包含-1才更新max
        boolean ex = false;
        for (int i = 0; i < s.length(); i++) {
            int ch = s.charAt(i) - 'a';
            int v = ch == a ? 1 : ch == b ? -1 : 0;

            if (v + pre < v) {
                ex = v == -1;
                pre = v;
            } else {
                ex |= v == -1;
                pre += v;
            }
            if (ex)
                max = Math.max(max, pre);
        }
        return Math.max(pre - 1, max);
    }

    public static void main(String[] args) {
        最大波动的子字符串 solution = new 最大波动的子字符串();
        int x = solution.largestVariance("ababab");
        System.out.println(x);


    }


}
